package codeRandomThoughts.Test42接雨水;

//跟双指针法相比,增加了动态规划求最高值的过程
//简化了许多次循环
//按列计算
public class Solution2 {
    public static int trap(int[] height) {
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];
        for (int i = 0; i < height.length; i++) {
            if (i == 0) leftMax[i] = height[i];
            else {
                leftMax[i] = Math.max(leftMax[i - 1], height[i]);
            }
        }
        for (int i = height.length - 1; i >= 0; i--) {
            if (i == height.length - 1) rightMax[i] = height[i];
            else {
                rightMax[i] = Math.max(rightMax[i + 1], height[i]);
            }
        }


        //每列雨水的高度等于左侧最高的柱子高度和右侧最高的柱子高度的最小值
        int sum = 0;//雨水总和
        for (int i = 1; i < height.length - 1; i++) {//第一列和最后一列不算
            int shortHeight = Math.min(leftMax[i], rightMax[i]);
            sum += (shortHeight - height[i]);
        }

        return sum;
    }

    public static void main(String[] args) {
        int[] height = {4, 2, 0, 3, 2, 5};
        System.out.println(trap(height));
    }
}
